package vip.zhenzicheng.algorithm.leetcode.dp;

/**
 * <a href="https://leetcode.cn/problems/maximum-subarray/">最大子数组和 [简单]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-14 13:31
 */
public class MaximumSubarray_53 {

  /*动态规划*/
  // public int maxSubArray(int[] nums) {
  //   int[] dp = new int[nums.length]; // 准备dp数组
  //   dp[0] = nums[0];
  //   int result = dp[0];
  //
  //   for (int i = 1; i < nums.length; i++) {
  //     dp[i] = Math.max(nums[i] + dp[i - 1], nums[i]);
  //     if (dp[i] > result) {
  //       result = dp[i];
  //     }
  //   }
  //   return result;
  // }

  /*优化版动态规划*/
  public int maxSubArray(int[] nums) {
    int result = nums[0], pre = nums[0];

    for (int i = 1; i < nums.length; i++) {
      pre = Math.max(nums[i], pre + nums[i]);
      if (pre > result) {
        result = pre;
      }
    }
    return result;
  }
}
